package easy;

import java.util.HashSet;
import java.util.Set;

public class numJewelsInStones {

    public static void main(String[] args) {
        String J = "aA";
        String S = "aAAbbbb";
        System.out.println(myCode(J, S));
    }

    /**
     * 将字符串换为字符数组，浪费了空间与时间
     *
     * @param jewels
     * @param stones
     * @return
     */
    public static int myCode(String jewels, String stones) {
        int sum = 0;
        for (int i = 0; i < stones.length(); i++) {
            for (int j = 0; j < jewels.length(); j++) {
                if (stones.charAt(i) == jewels.toCharArray()[j]) {
                    sum++;
                }
            }
        }
        return sum;
    }

    /**
     * 使用charAt获取当前字符，节约时间与空间
     * 时间复杂度为O(mn) 时间复杂度较高
     * 空间复杂度为O(1) 只需要维护常量的额外空间
     *
     * @param jewels
     * @param stones
     * @return
     */
    public static int ans(String jewels, String stones) {
        int sum = 0;
        for (int i = 0; i < stones.length(); i++) {
            char stone = stones.charAt(i);
            for (int j = 0; j < jewels.length(); j++) {
                char jewel = jewels.charAt(j);
                if (stone == jewel) {
                    sum++;
                    break;
                }
            }
        }
        return sum;
    }

    /**
     * 使用Map存储jewel,再遍历一次stones,如果stones中的字符在Map中存在,那么就是一个宝石
     * 时间复杂度O(m+n) 较低
     * 空间复杂度O(m) 是字符串jewel的长度
     * @param jewels
     * @param stones
     * @return
     */
    public int numJewelsInStones(String jewels, String stones) {
        int jewelsCount = 0;
        Set<Character> jewelsSet = new HashSet<Character>();
        int jewelsLength = jewels.length(), stonesLength = stones.length();
        for (int i = 0; i < jewelsLength; i++) {
            char jewel = jewels.charAt(i);
            jewelsSet.add(jewel);
        }
        for (int i = 0; i < stonesLength; i++) {
            char stone = stones.charAt(i);
            if (jewelsSet.contains(stone)) {
                jewelsCount++;
            }
        }
        return jewelsCount;
    }
}
